Factor Graph and the Junction Tree Algorithm

Factor Graph

VS DGM & UGM

DGM and UGM: allow a global function of several variables to be expressed as a product of factors over subsets of those variables, designed for conditional independence or potentials.
Factor graphs: make this decomposition explicit by introducing additional nodes for the factors in addition to the nodes representing the variables, designed for more explicit details of the factorization.

Definition

$p(x_1,…,x_n)=\prod_sf_s(x_s)\qquad x_s\in\{x_1,…,x_n\}$
Each $f_s$ is a function of a set of $x_s$.

Convert a UGM into a factor graph

Representing the potential functions over cliques as factors $f_s(x_s)$.
Different factor graphs may correspond to the same DGM/UGM.
Loopy DGM/UGM becomes a tree when converted to factor graph.

Goal: compute all singleton marginal probabilities.

Messages

From variable to factor:

$$v_{is}=\prod_{t\in N(i)-s}\mu_{ti}$$

and $v_{is}=1$ when $x_i$ is a leaf.
From factor to variable:

$$\mu_{si}=\sum_{x\in N(s)-i}(f_s(x_{N(s)})\prod_{j\in N(s)-i}v_{js})$$

and $\mu_{si}=f_s$ when $f_s$ is a leaf.
This message is equal to $m_{ji}$ in UGM.

Therefore, we can get the marginalization probability:

$$p(x_i)\propto\prod_{s\in N(i)}\mu_{si}(x_i)=v_{is}\mu_{si}\qquad \forall s\in N(i)$$

since $v_{is} = \prod_{t\in N(i)-s}\mu_{ti}$

Sum-product algorithm of factor graph

Max-product Algorithm

Junction Tree